// 题目描述
// 讨论 (169)
// LCR 017. 最小覆盖子串
// 困难
// 108
// 给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。
// 如果 s 中存在多个符合条件的子字符串，返回任意一个。
//   注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
//   示例 1：
// 输入：s = "ADOBECODEBANC", t = "ABC"
// 输出："BANC"
// 解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'
// 示例 2：
// 输入：s = "a", t = "a"
// 输出："a"
// 示例 3：
// 输入：s = "a", t = "aa"
// 输出：""
// 解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
//   提示：
// 1 <= s.length, t.length <= 105
// s 和 t 由英文字母组成
//   进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
//   注意：本题与主站 76 题相似（本题答案不唯一）：https://leetcode-cn.com/problems/minimum-window-substring/
// 通过次数
// 33K
// 提交次数
// 64.9K
// 通过率
// 50.9%
// https://leetcode.cn/problems/M1oyTv

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  const needs = new Map()
  for (let ch of t) {
    needs.set(ch, (needs.get(ch) || 0) + 1)
  }
  const win = new Map()
  const ans = [Infinity, '']

  let [left, right, valid] = [0, 0, 0]
  while (right < s.length) {
    // 放入窗口
    const ch = s[right++] // 初始窗口内字符串不是涵盖 t 所有字符的最小子串
    win.set(ch, (win.get(ch) || 0) + 1)
    // 判断异位词的固定套路，维护两个 map 和一个 valid 变量
    if (needs.has(ch)) {
      if (needs.get(ch) === win.get(ch)) {
        ++valid
      }
    }

    // 收缩窗口的条件则是：窗口内字符串是涵盖 t 所有字符的最小子串
    while (valid === needs.size) {
      const curLen = right - left
      if (curLen < ans[0]) {
        ans[0] = curLen
        ans[1] = s.slice(left, right)
      }

      // 弹出窗口
      const last = s[left++]
      if (needs.has(last)) {
        if (needs.get(last) === win.get(last)) {
          --valid
        }
      }
      win.set(last, (win.get(last) || 0) - 1)
    }
  }

  return ans[1]
}

console.log(
  minWindow(
    "ADOBECODEBANC",
    "ABC"
  )
)












